//169. 多数元素
//思路：先排序，再对相邻元素处理，记录出某个数字出现的个数，与n/2比较，当大于等于就返回该数字


#include <vector>
#include <algorithm>

using namespace std;

class Solution 
{
public:
    int majorityElement(vector<int>& nums) 
    {
        sort(nums.begin(), nums.end());
        int count = 1, ans = INT_MIN;
        int i = 1, n = nums.size();
        while(i < n)
        {
            if(nums[i-1] == nums[i])
            {
                count++;
            }
            else
            {
                if((double)count >= n/2.0)
                {
                    ans = nums[i-1];
                    break;
                }
                count = 1;
            }
            i++;
        }
        return ans == INT_MIN ? nums[n-1] : ans;
    }
};